package leetcode_ago.map_and_set.hash;

/**
 * @author 美女
 * @date 2022/03/22 11:21
 **/

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 请你判断一个9x9的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 * 数字1-9在每一行只能出现一次。
 * 数字1-9在每一列只能出现一次。
 * 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * 空白格用 '.' 表示
 * 分析：使用哈希表记录某行某列或某个3*3小方块区域出现过哪些数字
 */
public class Num36_IsValidSudoku {
    public boolean isValidSudoku(char[][] board) {
        Map<Integer, Set<Integer>> row=new HashMap<>();
        Map<Integer, Set<Integer>> col=new HashMap<>();
        Map<Integer, Set<Integer>> area=new HashMap<>();
        //将对应行列及区域的所有元素存入set集合
        for (int i = 0; i < 9; i++) {
            row.put(i,new HashSet<>());//0行对应val:0行所有元素...
            col.put(i,new HashSet<>());
            area.put(i,new HashSet<>());
        }
        //遍历九宫格，判断九宫格元素v是否在Set集合中，在false,否则v添加进Set继续循环判断，直到结束未返回false就说明书写的数独正确
        //注意：空格元素用‘.’代替
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                char c=board[i][j];
                //每个小区块的索引
                int index=(i/3)*3+j/3;
                //每行每列对应元素
                int v=c-'0';
                if(c!='.'){
                    //元素不为空时，开始判断该元素是否重复包含在Set集合中
                    //row.get(i):取得i行对应的所有元素
                    if(row.get(i).contains(v)||col.get(j).contains(v)||area.get(index).contains(v)){
                        return false;
                    }
                    //此时元素不包含在Set集合中，向集合中加入该元素
                    row.get(i).add(v);
                    col.get(j).add(v);
                    area.get(index).add(v);
                }
            }
        }
        //循环走完还未发现重复，则数独正确
        return true;
    }
}
